Graph Theory

1. Graph

1.1. Definition

\[ G:=(V, E) \] Pair of a set $ V $ of vertices $ v_i $ and a set $ E $ of edges $ \{ v_i, v_j \} $.

1.1.1. Directed Graph

The edges are ordered, and represented by pair $ (v_i, v_j) $.

1.1.2. Multigraph

$ E $ is a multiset which allows multiple edges with same endpoints.

1.1.3. Loop

An edge to itself is called a loop. The existence of loops can be made clear by adding with loops.

1.2. Order

$|G|$

The number of vertices $ |V| $ in a graph $G$.

1.3. Degree

$ d(v) $

Degree, or valency, of a vertex is the number of edges that are incident to it.

1.4. Subgraph

\(G_2

(Strict) subgraph $G_2 = (V_2, E_2) $ is a graph satisfying $ V_2 \subseteq V_1 $ (or $V_2\subset V_1$) and $ E_2 \subseteq E_1 $ (or $E_2\subset E_1$)

1.5. Boundary

$\partial G_2$

Boundary $ \partial G_2 $ of $G_2 \subset G_1$ is a set of edge $ e \in E_1 $ that is connected to $V_2$ but not in $E_2$.

1.6. Tree

An acyclic graph is an unrooted tree, in which case the leaves are the nodes with degree one.
The root of a tree can be chosen.

1.6.1. Binary Tree

1.6.1.1. Heap

In a max-heap (or min-heap), two child nodes are less than (or greater than) the parent.
((65dc61b0-e3ab-49be-9b51-aa1acde0e5eb))

1.6.1.2. Binary Search Tree

The left child is less than the parent, and the right child is greater than the parent.

It is a form of Binary Search

1.6.2. Spanning Tree

Subgraph that is also a tree that contains every vertices.

1.7. Bipartite Graph

Graph whose vertices can be divided into two disjoint and independent sets $ U $ and $ V $. That is, every edge connects a vertex in $ U $ to one in $ V $ .

1.7.1. Complete Bipartite Graph

Biclique

Every vertex of $ U $ is connected to every vertex of $ V $ .

1.8. d-Regular Graph

Graph in which every vertex has degree d.

2. Graph Traversal

2.1. Path

Sequence of vertices with edges between them, where all vertices are distinct.

2.2. Cycle

Path that starts and ends on the same vertex.

2.3. Trail

Sequence of vertices with edges between them, where all edges are distinct.

2.4. Circuit

Trail that starts and ends on the same vertex.

2.5. Euler Trail

aka Euler Path
Trail that includes every edges.

2.6. Euler Circuit

Euler Trail that starts and ends on the same vertex.

3. Algebraic Graph Theory

3.1. Adjacency Matrix

A matrix that represents the graph efficiently.
For a undirected graph, the adjacency matrix is symmetric.
Adjacency List, which is an array of list of vertices that are connected, is also available.
$a_{ij} = 1$ if $(n_i, n_j) \in E$.

3.2. Incidence Matrix

For a directed graph, \[ B_{ik} := \begin{cases} 1, & \text{edge $k$ points towards node $i$},\\ -1, & \text{edge $k$ leaves node $i$},\\ 0, &\text{otherwise}. \end{cases} \]

It is a linear map $ B: \mathbb{R}^{|E|} \to \mathbb{R}^{|V|} $, in other words, the linear map from the formal vector space of edges, to the formal vector space of vertices.

e.g. $B(e_1 = (n_1, n_2)) = n_2 - n_1$.

3.2.1. Properties

The elements of the null space are the cycles.

3.3. Laplacian Matrix

3.3.1. Degree Matrix

Diagonal matrix in which $ i $th entry is the degree of the $ i $th vertex.

3.3.2. Definition

\[ L = D - A \] where $D$ is the degree matrix and $A$ is the adjacency matrix.

After distributing the degree to each adjacent vertex, we see: \[ (Lf)_i = \sum_{j,i \sim j} f(i) - f(j) \] where $ \sim $ denotes the adjacency relation.

It calculates the "concavity" at each vertex, similar to the Laplace operator $ \nabla^2 $ in multivariable calculus.

3.3.3. Properties

\[ L = BB^{\mathsf{T}} \] where $ B $ is the incidence matrix.

3.4. Kirchhoff's Theorem

Any $ (i,i) $-minor of Laplacian matrix is the possible number of spanning tree.

4. Spectral Graph Theory

4.1. Spectrum

$ Lf = \lambda f $

The set of eigenvalues $ \lambda $ of Laplacian matrix $ L $ is called the spectrum of a graph.

4.1.1. Properties

Let $ f $ be a normalized eigenvector with eigenvalue $ \lambda $. Multiplying both side of eigenvalue equation by $ f^{\mathsf{T}} $, we get: \[ \lambda = \sum_i (f(i) \sum_{j, i\sim j} (f(i) - f(j))) = \sum_{i < j, i\sim j} (f(i) - f(j))^2. \]

It follows that

$L$ is semi-positive definite.
0 is always the eigenvalue of $L$.
The smaller the eigenvalue the smoother the eigenvectors. The smaller the eigenvalue, the less connected the graph is.

4.2. Alon-Boppana Bound

For a $ d $-regular graph with diameter $ m $: \[ \lambda_2 \ge 2 \sqrt{d-1} - \frac{2 \sqrt{d-1} - 1}{\lfloor m/2 \rfloor} \] where $ \lambda_2 $ is the second largest eigenvalue of adjacency matrix.

5. Connection

5.1. Connectedness

In an undirected graph $ G $, two vertices $ v $ and $ u $ are called connected if $ G $ contains a path from $ u $ to $ v $.

A graph is said to be connected if all verticies are pairwise connected.

A graph with single vertex is vacuously connected.

A directed graph is called weakly connected

5.2. Component

5.2.1. Definition

A component of an undirected graph is a connected subgraph that is not part of strictly larger connected subgraph.

5.3. Connectivity

The minimum number of elements

5.4. Expansion Rate

$ \Phi(S) $

Expansion rate of $S \subset G$ is defined as \[ \Phi(S) :=\frac{|\partial S|}{\min(|S|, |S^{\mathsf{c}}|)}. \]

5.5. Cheeger Constant

$ h(G), \Phi^{*}(G) $
Isoperimetric Number, Edge Expansion

For the measure of well-connectedness, we use the the minimum expansion rates, called Cheeger constant: \[ h(G) := \min_{\begin{smallmatrix}S < G \\ |S| \le n/2 \end{smallmatrix}} \Phi(S). \]

Low $\lambda_2$ can be achieved with high probability using random $n$ cycles.

5.6. Cheeger Inequality

5.6.1. For Connected Graph

\[ \frac{\lambda_2}{2} \le h(G) \le \sqrt{2\lambda_2\Delta(G)} \] where $ \lambda_2 $ is the spectral gap (second smallest - smallest) of the Laplacian matrix, and $ \Delta(G) $ is the maximum degree in $ G $.

5.6.2. For d-Regular Graph

Cheeger inequalities for $d$-regular graph is given by: \[ \frac{1}{2}(d - \lambda_2) \le h(G)\le \sqrt{2d(d-\lambda_2)} \] where $d$ is the degree of a graph which is also the first eigenvalue of its adjacency matrix, and $\lambda_2$ is the second eigenvalue.

5.7. Diameter

The minimum length of path that can connect any two nodes: \[ D := \max_{v, w \in V}\left(\min_{P \in \mathrm{Path}(v, w)} |P| \right). \]

5.8. Expander Graph

Sparse and strongly connected graph

6. Cyclomatic Number

Circuit Rank, Cycle Rank, Corank, Nullity

The number of independent cycles, that is, the size of a cycle basis.

It is also the minumum number of edges that must be removed from the graph to break all its cycles.

Cyclomatic number $ r $ is easily computed using the formula: \[ r = e - v + c \] where $ e $ is the number of edges, $ v $ is the number of vertices, $ c $ is the number of connected components.

7. Extremal Graph Theory

Hypergraphs and Acute Triangles | #SoMEpi - YouTube

8. Vertex Cover

Subset of vertices that every edge touches one of the vertices in this set.

River Crossings (and Alcuin Numbers) - Numberphile - YouTube

8.1. Alcuin Number

The minimum size of the boat in order to carry all the items to the other side of the river.